package com.yoshino.leetcode.oneHundred.sixth;

import java.util.*;

class Solution {
    public int[] levelOrder1(TreeNode root) {
        // 底层遍历
        if (root == null) {
            return new int[0];
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            res.add(root.val);
            if (root.left != null) {
                queue.add(root.left);
            }
            if (root.right != null) {
                queue.add(root.right);
            }
        }
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> temp = new ArrayList<>();
        queue.add(root);
        queue.add(null);
        while (!queue.isEmpty()) {
            root = queue.poll();
            if (root == null) {
                return res;
            }
            temp.add(root.val);
            if (root.left != null) {
                queue.add(root.left);
            }
            if (root.right != null) {
                queue.add(root.right);
            }
            if (queue.peek() == null) {
                res.add(temp);
                queue.poll();
                if (queue.isEmpty()) {
                    return res;
                }
                queue.add(null);
                temp = new ArrayList<>();
            }
        }
        return res;
    }

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> temp = new ArrayList<>();
        queue.add(root);
        queue.add(null);
        int tot = 1;
        while (!queue.isEmpty()) {
            root = queue.poll();
            temp.add(root.val);
            if (root.left != null) {
                queue.add(root.left);
            }
            if (root.right != null) {
                queue.add(root.right);
            }
            if (queue.peek() == null) {
                queue.poll();
                // 在 2 的基础上增加偶数层 反转
                if (tot == 1) {
                    res.add(temp);
                    tot++;
                } else {
                    Collections.reverse(temp);
                    res.add(temp);
                    tot--;
                }
                if (queue.isEmpty()) {
                    return res;
                }
                temp = new ArrayList<>();
                queue.add(null);
            }
        }
        return res;
    }
}